package com.lfg.leetcode.leetcode200;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class No239maxSlidingWindow {

    public static void main(String[] args) {
        int[] ret = maxSlidingWindow(new int[]{7, 2, 4}, 2);
        for (int i : ret) {
            System.out.println(i);
        }
    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int length = nums.length - k + 1;
        if (length <= 0 || k == 0) {
            return new int[0];
        }
        int[] ret = new int[length];

        Queue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int i = 0;
        for (; i < k - 1 && i < nums.length; i++) {
            queue.add(nums[i]);
        }
        int index = 0;
        for (; i < nums.length; i++) {
            queue.add(nums[i]);
            ret[index++] = queue.peek();
            queue.remove(nums[i - k + 1]);
        }
        return ret;
    }


    public static int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length - k + 1;
        if (k == 0 || nums.length == 0 || length <= 0) {
            return new int[0];
        }
        int[] ret = new int[length];
        int index = 0;
        LinkedList<Integer> list = new LinkedList<Integer>();
        int i = 0;
        for (; i < nums.length; i++) {
            if (list.size() > 0 && list.peekFirst() <= i - k) {
                list.pollFirst();
            }
            while (list.size() > 0 && nums[list.peekLast()] < nums[i]) {
                list.pollLast();
            }
            list.addLast(i);
            if (i - k + 1 >= 0) {
                ret[index++] = nums[list.peekFirst()];
            }
        }
        return ret;
    }
}
